<!doctype html>

<html>
<head>
  <link rel="shortcut icon" href="static/images/favicon.ico" type="image/x-icon">
  <title>inversionmap.js (Closure Library API Documentation - JavaScript)</title>
  <link rel="stylesheet" href="static/css/base.css">
  <link rel="stylesheet" href="static/css/doc.css">
  <link rel="stylesheet" href="static/css/sidetree.css">
  <link rel="stylesheet" href="static/css/prettify.css">

  <script>
     var _staticFilePath = "static/";
     var _typeTreeName = "goog";
     var _fileTreeName = "Source";
  </script>

  <script src="static/js/doc.js">
  </script>


  <meta charset="utf8">
</head>

<body onload="grokdoc.onLoad();">

<div id="header">
  <div class="g-section g-tpl-50-50 g-split">
    <div class="g-unit g-first">
      <a id="logo" href="index.html">Closure Library API Documentation</a>
    </div>

    <div class="g-unit">
      <div class="g-c">
        <strong>Go to class or file:</strong>
        <input type="text" id="ac">
      </div>
    </div>
  </div>
</div>

<div class="clear"></div>

<h2><a href="local_closure_goog_structs_inversionmap.js.html">inversionmap.js</a></h2>

<pre class="prettyprint lang-js">
<a name="line1"></a>// Copyright 2008 The Closure Library Authors. All Rights Reserved.
<a name="line2"></a>//
<a name="line3"></a>// Licensed under the Apache License, Version 2.0 (the &quot;License&quot;);
<a name="line4"></a>// you may not use this file except in compliance with the License.
<a name="line5"></a>// You may obtain a copy of the License at
<a name="line6"></a>//
<a name="line7"></a>//      http://www.apache.org/licenses/LICENSE-2.0
<a name="line8"></a>//
<a name="line9"></a>// Unless required by applicable law or agreed to in writing, software
<a name="line10"></a>// distributed under the License is distributed on an &quot;AS-IS&quot; BASIS,
<a name="line11"></a>// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
<a name="line12"></a>// See the License for the specific language governing permissions and
<a name="line13"></a>// limitations under the License.
<a name="line14"></a>
<a name="line15"></a>/**
<a name="line16"></a> * @fileoverview Provides inversion and inversion map functionality for storing
<a name="line17"></a> * integer ranges and corresponding values.
<a name="line18"></a> *
<a name="line19"></a> */
<a name="line20"></a>
<a name="line21"></a>goog.provide(&#39;goog.structs.InversionMap&#39;);
<a name="line22"></a>
<a name="line23"></a>goog.require(&#39;goog.array&#39;);
<a name="line24"></a>
<a name="line25"></a>
<a name="line26"></a>
<a name="line27"></a>/**
<a name="line28"></a> * Maps ranges to values.
<a name="line29"></a> * @param {Array.&lt;number&gt;} rangeArray An array of monotonically
<a name="line30"></a> *     increasing integer values, with at least one instance.
<a name="line31"></a> * @param {Array.&lt;T&gt;} valueArray An array of corresponding values.
<a name="line32"></a> *     Length must be the same as rangeArray.
<a name="line33"></a> * @param {boolean=} opt_delta If true, saves only delta from previous value.
<a name="line34"></a> * @constructor
<a name="line35"></a> * @template T
<a name="line36"></a> */
<a name="line37"></a>goog.structs.InversionMap = function(rangeArray, valueArray, opt_delta) {
<a name="line38"></a>  /**
<a name="line39"></a>   * @protected {Array}
<a name="line40"></a>   */
<a name="line41"></a>  this.rangeArray = null;
<a name="line42"></a>
<a name="line43"></a>  if (rangeArray.length != valueArray.length) {
<a name="line44"></a>    // rangeArray and valueArray has to match in number of entries.
<a name="line45"></a>    return null;
<a name="line46"></a>  }
<a name="line47"></a>  this.storeInversion_(rangeArray, opt_delta);
<a name="line48"></a>
<a name="line49"></a>  /** @protected {Array.&lt;T&gt;} */
<a name="line50"></a>  this.values = valueArray;
<a name="line51"></a>};
<a name="line52"></a>
<a name="line53"></a>
<a name="line54"></a>/**
<a name="line55"></a> * Stores the integers as ranges (half-open).
<a name="line56"></a> * If delta is true, the integers are delta from the previous value and
<a name="line57"></a> * will be restored to the absolute value.
<a name="line58"></a> * When used as a set, even indices are IN, and odd are OUT.
<a name="line59"></a> * @param {Array.&lt;number?&gt;} rangeArray An array of monotonically
<a name="line60"></a> *     increasing integer values, with at least one instance.
<a name="line61"></a> * @param {boolean=} opt_delta If true, saves only delta from previous value.
<a name="line62"></a> * @private
<a name="line63"></a> */
<a name="line64"></a>goog.structs.InversionMap.prototype.storeInversion_ = function(rangeArray,
<a name="line65"></a>    opt_delta) {
<a name="line66"></a>  this.rangeArray = rangeArray;
<a name="line67"></a>
<a name="line68"></a>  for (var i = 1; i &lt; rangeArray.length; i++) {
<a name="line69"></a>    if (rangeArray[i] == null) {
<a name="line70"></a>      rangeArray[i] = rangeArray[i - 1] + 1;
<a name="line71"></a>    } else if (opt_delta) {
<a name="line72"></a>      rangeArray[i] += rangeArray[i - 1];
<a name="line73"></a>    }
<a name="line74"></a>  }
<a name="line75"></a>};
<a name="line76"></a>
<a name="line77"></a>
<a name="line78"></a>/**
<a name="line79"></a> * Splices a range -&gt; value map into this inversion map.
<a name="line80"></a> * @param {Array.&lt;number&gt;} rangeArray An array of monotonically
<a name="line81"></a> *     increasing integer values, with at least one instance.
<a name="line82"></a> * @param {Array.&lt;T&gt;} valueArray An array of corresponding values.
<a name="line83"></a> *     Length must be the same as rangeArray.
<a name="line84"></a> * @param {boolean=} opt_delta If true, saves only delta from previous value.
<a name="line85"></a> */
<a name="line86"></a>goog.structs.InversionMap.prototype.spliceInversion = function(
<a name="line87"></a>    rangeArray, valueArray, opt_delta) {
<a name="line88"></a>  // By building another inversion map, we build the arrays that we need
<a name="line89"></a>  // to splice in.
<a name="line90"></a>  var otherMap = new goog.structs.InversionMap(
<a name="line91"></a>      rangeArray, valueArray, opt_delta);
<a name="line92"></a>
<a name="line93"></a>  // Figure out where to splice those arrays.
<a name="line94"></a>  var startRange = otherMap.rangeArray[0];
<a name="line95"></a>  var endRange =
<a name="line96"></a>      /** @type {number} */ (goog.array.peek(otherMap.rangeArray));
<a name="line97"></a>  var startSplice = this.getLeast(startRange);
<a name="line98"></a>  var endSplice = this.getLeast(endRange);
<a name="line99"></a>
<a name="line100"></a>  // The inversion map works by storing the start points of ranges...
<a name="line101"></a>  if (startRange != this.rangeArray[startSplice]) {
<a name="line102"></a>    // ...if we&#39;re splicing in a start point that isn&#39;t already here,
<a name="line103"></a>    // then we need to insert it after the insertion point.
<a name="line104"></a>    startSplice++;
<a name="line105"></a>  } // otherwise we overwrite the insertion point.
<a name="line106"></a>
<a name="line107"></a>  var spliceLength = endSplice - startSplice + 1;
<a name="line108"></a>  goog.partial(goog.array.splice, this.rangeArray, startSplice,
<a name="line109"></a>      spliceLength).apply(null, otherMap.rangeArray);
<a name="line110"></a>  goog.partial(goog.array.splice, this.values, startSplice,
<a name="line111"></a>      spliceLength).apply(null, otherMap.values);
<a name="line112"></a>};
<a name="line113"></a>
<a name="line114"></a>
<a name="line115"></a>/**
<a name="line116"></a> * Gets the value corresponding to a number from the inversion map.
<a name="line117"></a> * @param {number} intKey The number for which value needs to be retrieved
<a name="line118"></a> *     from inversion map.
<a name="line119"></a> * @return {T|null} Value retrieved from inversion map; null if not found.
<a name="line120"></a> */
<a name="line121"></a>goog.structs.InversionMap.prototype.at = function(intKey) {
<a name="line122"></a>  var index = this.getLeast(intKey);
<a name="line123"></a>  if (index &lt; 0) {
<a name="line124"></a>    return null;
<a name="line125"></a>  }
<a name="line126"></a>  return this.values[index];
<a name="line127"></a>};
<a name="line128"></a>
<a name="line129"></a>
<a name="line130"></a>/**
<a name="line131"></a> * Gets the largest index such that rangeArray[index] &lt;= intKey from the
<a name="line132"></a> * inversion map.
<a name="line133"></a> * @param {number} intKey The probe for which rangeArray is searched.
<a name="line134"></a> * @return {number} Largest index such that rangeArray[index] &lt;= intKey.
<a name="line135"></a> * @protected
<a name="line136"></a> */
<a name="line137"></a>goog.structs.InversionMap.prototype.getLeast = function(intKey) {
<a name="line138"></a>  var arr = this.rangeArray;
<a name="line139"></a>  var low = 0;
<a name="line140"></a>  var high = arr.length;
<a name="line141"></a>  while (high - low &gt; 8) {
<a name="line142"></a>    var mid = (high + low) &gt;&gt; 1;
<a name="line143"></a>    if (arr[mid] &lt;= intKey) {
<a name="line144"></a>      low = mid;
<a name="line145"></a>    } else {
<a name="line146"></a>      high = mid;
<a name="line147"></a>    }
<a name="line148"></a>  }
<a name="line149"></a>  for (; low &lt; high; ++low) {
<a name="line150"></a>    if (intKey &lt; arr[low]) {
<a name="line151"></a>      break;
<a name="line152"></a>    }
<a name="line153"></a>  }
<a name="line154"></a>  return low - 1;
<a name="line155"></a>};
</pre>


</body>
</html>
